Search for: All records

In this paper, we consider the classic fair division problem of allocating m divisible items to n agents with linear valuations over the items. We define novel notions of fair shares from the perspective of individual agents via the cake-cutting process. These shares generalize the notion of proportionality by taking into account the valuations of other agents via constraints capturing envy. We study what fraction (approximation) of these shares are achievable in the worst case, and present tight and non-trivial approximation bounds as a function of n and m. In particular, we show a tight approximation bound of Θ(√n) for various notions of such shares. We show this bound via a novel application of dual fitting, which may be of independent interest. We also present a bound of O(m^(2/3)) for a strict notion of share, with an almost matching lower bound. We further develop weaker notions of shares whose approximation bounds interpolate smoothly between proportionality and the shares described above. We finally present empirical results showing that our definitions lead to more reasonable shares than the standard fair share notion of proportionality. 

Background:A core challenge in managing diabetes is predicting glycemic responses to meals. Prior work identified significant interindividual variation in responses and developed personalized forecasts. However, intraindividual variation is still not well understood, and the most accurate approaches require invasive microbiome data. We aimed to investigate (1) whether postprandial glycemic responses (PPGRs) can be predicted with limited data and (2) sources of intraindividual variation. Methods:We used data collected from 397 people with Type 1 Diabetes (T1DEXI) and 100 people with Type 2 Diabetes (ShanghaiT2DM) who wore continuous glucose monitors (CGMs) and logged meals. Using dietary, demographic, and temporal features, we predicted 2 hours PPGR, and peak 2 hours postprandial glucose rise (Glu_max). We evaluated the contribution of food features (eg, macronutrients, food category) and use of personal training data and investigated intraindividual variability in responses. Results:We achieved comparable accuracy to prior work for PPGR (T1DEXI R = 0.61, ShanghaiT2DM R = 0.72) and Glu_max(T1DEXI R = 0.64, ShanghaiT2DM R = 0.73), without using invasive data like microbiome. Including food category features led to higher accuracy than macronutrients alone. Analysis of glycemic responses to duplicate meals identified time of day (PPGR: T1DEXI P < .05 for lunch, ShanghaiT2DM P < .001 for lunch and dinner) and menstrual cycle (Glu_max: P < .05 for perimenstrual) as sources of variability. Conclusions:We demonstrate that in individuals with T1D and T2D, glycemic responses to meals can be predicted without personalized training data or invasive physiological data.